package brzozowski;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import helpers.HandleList;
import interfaces.Automaton;
import interfaces.State;
import interfaces.Transition;
import exceptions.NotDeterministInitalStateException;
import exceptions.NotDeterministTransitionException;
import exceptions.UnknownInitialStateException;
import exceptions.UnknownTerminalStateException;
import automaton.DFA;
import automaton.FA;
import automaton.StateImpl;
import automaton.TransitionImpl;

/**
 * @author TRAN NHAT QUANG
 *
 */

public class Brzozowski {
	/**
	 * implement Brzozoski's algorithm
	 * @param automata
	 * @return should be a DFA
	 * @throws UnknownInitialStateException
	 * @throws UnknownTerminalStateException
	 * @throws NotDeterministInitalStateException
	 * @throws NotDeterministTransitionException
	 */
	public static DFA doBrzozoski(Automaton automata) throws UnknownInitialStateException, UnknownTerminalStateException, NotDeterministInitalStateException, NotDeterministTransitionException
	{		
		/*System.out.println("------------------Reverse----------------------");
		FA t1 = getReversedAutomata(automata);
		System.out.println("------------------Determine----------------------");
		DFA t2 = convertToDFA(t1);
		System.out.println("------------------Reverse----------------------");
		FA t3 = getReversedAutomata(t2);
		System.out.println("------------------Determine----------------------");
		return convertToDFA(t3);*/
		return convertToDFA(getReversedAutomata(convertToDFA(getReversedAutomata(automata))));
	}
	
	/**
	 * Reverse automata
	 * @throws UnknownTerminalStateException 
	 * @throws UnknownInitialStateException 
	 */
	@SuppressWarnings("unchecked")
	public static FA getReversedAutomata(Automaton automata) throws UnknownInitialStateException, UnknownTerminalStateException
	{
		//Stopwatch sw = new Stopwatch();
		Transition<String>[] transArray = new TransitionImpl[automata.getTransitions().length];

		//reverse transitions
		transArray = getReversedTransitions(automata);
		
		//reverse state
		try 
		{
			FA rs = new FA(transArray);

			rs.reverseStates();
			
			//System.out.println("-->R: "  + sw.elapsedTime());
			
			return rs;
		} 
		catch (UnknownInitialStateException se) 
		{
			System.out.println(se.getMessage());
		}
		catch (UnknownTerminalStateException e)
		{
			System.out.println(e.getMessage());
		}
		
		
		return null;
	}
	
	/**
	 * get reversed transitions of an automata
	 * @return
	 * @throws UnknownTerminalStateException 
	 * @throws UnknownInitialStateException 
	 */
	private static Transition<String>[] getReversedTransitions(Automaton automata) throws UnknownInitialStateException, UnknownTerminalStateException
	{
		//List<Transition<String>> ls = new ArrayList<>();
		Transition<String>[] array = automata.getTransitions();
		@SuppressWarnings("unchecked")
		Transition<String>[] transArray = new TransitionImpl[array.length];
		List<State> newStates = new ArrayList<>();
		List<State> states = new ArrayList<>();
		
		states.addAll(automata.getFA().keySet());
		
		//create new state
		for (State s: states)
		{
			State temp = new StateImpl(s.label().toString(),s.initial(),s.terminal());
			newStates.add(temp);
		}
		//reverse transitions
		for (int i = 0; i<array.length; i++)
		{
			transArray[i] = array[i];
			
			// create new transition
			State oldSource = array[i].source();
			State oldTarget = array[i].target();
			State newSource = newStates.get(states.indexOf(oldSource));
			State newTarget = newStates.get(states.indexOf(oldTarget));
			
			transArray[i] = new TransitionImpl<String>(newSource,newTarget,array[i].label());
		}
		
		for (Transition<String> tempTran: transArray)
			if (tempTran instanceof TransitionImpl)
				((TransitionImpl<String>) tempTran).reversedTransition();
		
		return transArray;
	}
	
	/**
	 * 
	 * @return
	 * @throws NotDeterministTransitionException 
	 * @throws NotDeterministInitalStateException 
	 * @throws UnknownInitialStateException
	 * @throws UnknownTerminalStateException
	 */
	public static DFA convertToDFA(Automaton automata) throws UnknownInitialStateException, NotDeterministInitalStateException, NotDeterministTransitionException
	{
		//System.out.println("=======ConvertToDFA========");
		// Initialize		
		FA tempFA = reduceInitState(automata); // store 1-initial-state-automata
		List<List<State>> listStates = new ArrayList<>(); // store set of targets
		Map<List<State>, State> mapping = new HashMap<>(); // store set of targets and their state
		List<Transition<String>> listTrans = new ArrayList<>(); // store new transitions
		int pos = 1; // position of checking-list-state
		int max = tempFA.getFA().keySet().size(); // maximum states
		
		List<State> initStates = emptyClosure(tempFA, tempFA.getInitStates(), max);

		listStates.add(initStates);
		mapping.put(initStates, generateInitState(initStates, "0"));
		
		if (listStates.get(0).size() > 1)
			max = max - 1;
		
		// Find new set of targets and store linking info
		for (int i=0; i< listStates.size(); i++)
		{
			State tempSource = HandleList.getStateInMapping(mapping, listStates.get(i));
			//System.out.println("--> " + i);
			for (String label: tempFA.getLabels())
			{
				if (label != "empty")
				{
					List<State> targets = moveDFA(tempFA, listStates.get(i), label, max);
					
					if (targets.size() > 0)
					{
						if (!HandleList.checkExistList(listStates, targets))
						{
							listStates.add(targets);
							mapping.put(targets, generateState(targets, pos+""));
							pos++;
						}
						
						try
						{
							//State source = HandleList.getStateInMapping(mapping, listStates.get(i));
							State target = HandleList.getStateInMapping(mapping, targets);
							
							listTrans.add(new TransitionImpl<String>(tempSource, target, label));
						}
						catch (Exception ex)
						{
							System.out.println("Convert to DFA: " + ex.getMessage());
						}
					}
				}
			}
		}
		
		@SuppressWarnings("unchecked")
		Transition<String>[] array = new TransitionImpl[listTrans.size()];
		listTrans.toArray(array);
		
		return new DFA(array);
	}
	
	/**
	 * Find the set of states linked by empty transition
	 * @param s
	 * @return
	 */	
	public static List<State> emptyClosure(Automaton automata, List<State> s, int max)
	{
		int size = 0;
		
		while (size != s.size())
		{
			size = s.size();
			for (State tempState: getTargets(automata, s, "empty", max))
				if (!s.contains(tempState))
					s.add(tempState);
		} 
		
		return s;
	}
	
	/**
	 * Find targets of states
	 */
	private static List<State> getTargets(Automaton automata, List<State> stateList, String label, int max)
	{
		List<State> rs = new ArrayList<>();
		
		for (State tempState: stateList)
		{
			for (State temp: getTargets(automata, tempState, label))
				if (!rs.contains(temp))
					rs.add(temp);
			
			if (rs.size() == max)
				return rs;
		}
		
		//System.out.println(rs.size());
		return rs;
	}
	
	public static List<State> getTargets(Automaton automata, State state, String label)
	{
		List<State> s = new ArrayList<>();

		try
		{
			for (Transition<String> t: automata.getFA().get(state).get(label))
			{
				s.add(t.target());
			}
		}
		catch (Exception ex)
		{
			//System.out.println("getTargets: " + ex.getMessage());
			// this.getFA().get(state).get(label) return null but it is all right.
		}
		
		return s;
	}
	
	/**
	 * Generate new state from set of states
	 */
	private static State generateState(List<State> input, String label)
	{
		boolean init = true;
		boolean term = false;
		
		for (State temp: input)
		{
			if (!temp.initial())
				init = false;
			if (temp.terminal())
				term = true;
		}
		
		return new StateImpl(label, init, term);
	}
	
	private static State generateInitState(List<State> input, String label)
	{
		boolean init = true;
		boolean term = false;
		
		for (State temp: input)
		{
			if (temp.terminal())
				term = true;
		}
		
		return new StateImpl(label, init, term);
	}
	
	/**
	 * Find the set of target through a label
	 * @param s
	 * @return
	 */
	private static List<State> moveDFA(Automaton automata, List<State> s, String label, int max)
	{
		List<State> rs = new ArrayList<>();
		
		rs.addAll(emptyClosure(automata, getTargets(automata, s, label, max), max));
		
		return rs;
	}
	
	private static FA reduceInitState(Automaton automata)
	{
		if (automata instanceof DFA)
			try {
				return new FA(automata.getTransitions());
			} catch (UnknownInitialStateException
					| UnknownTerminalStateException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		
		return (FA) automata.reduceInitState();
	}
}
